package leetcode.code1123;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import leetcode.helper.tree.TreeNode;

public class Solution {

	Map<Integer, Set<Integer>> map;
	TreeNode ans;
	boolean flag;

	public TreeNode lcaDeepestLeaves(TreeNode root) {
		map = new HashMap<>();
		int d = d(root, 0);
		Set<Integer> l = map.get(d);
		f(root, l);
		return ans;
	}

	private int f(TreeNode root, Set<Integer> l) {
		if (root == null) {
			return 0;
		}
		int L = f(root.left, l);
		int R = f(root.right, l);
		int cur = L + R;
		cur += l.contains(root.val) ? 1 : 0;
		if (cur == l.size() && !flag) {
			flag = true;
			ans = root;
		}
		return cur;
	}

	private int d(TreeNode root, int h) {
		if (root == null) {
			return 0;
		}
		map.computeIfAbsent(h, key -> new HashSet<>()).add(root.val);
		int d = h;
		d = Math.max(d, d(root.left, h + 1));
		d = Math.max(d, d(root.right, h + 1));
		return d;
	}
}
